package com.zxlfysj.linkedlist;

import java.util.Stack;

/**
 * 单链表
 * @author yangshujing
 * @create 2020-08-14 20:34
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1, "潘森", "战争之王");
        HeroNode hero2 = new HeroNode(2, "贾克斯", "武器大师");
        HeroNode hero3 = new HeroNode(3, "拉克丝", "光辉女郎");
        HeroNode hero4 = new HeroNode(4, "安妮", "黑暗之女");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);

        singleLinkedList.reverse();
        singleLinkedList.list();

        //反向打印单链表
        singleLinkedList.reversePrint();


    }
}

class SingleLinkedList {
    //初始化一个头节点，头节点不要动，不存放具体的数据
    private HeroNode head = new HeroNode(0, "", "");

    //添加节点到单向链表
    public void add(HeroNode heroNode) {
         //head节点不能动，使用辅助指针temp
        HeroNode temp = head;
        //遍历找到当前链表的最后节点
        while (true) {
            if(temp.next == null) {
                break;
            }
            //辅助指针后移
            temp = temp.next;
        }
        //将最后节点的next指向新的节点
        temp.next = heroNode;
    }

    //删除节点,不能自我删除，需要找到要删除节点的前一个节点
    public void del(int no) {
        if(head.next == null) {
            System.out.println("链表空");
            return;
        }
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if(temp.next == null) {
                break;
            }
            if(temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag) {
            temp.next = temp.next.next;
        } else{
            System.out.println("没有找到");
        }

    }

    //反转单链表
    public void reverse() {
        //如果链表为空或者只有一个节点，无需反转
        if(head.next == null || head.next.next == null) {
            return;
        }
        //创建一个新的头节点，也就是新链表
        HeroNode newhead = new HeroNode(0, "", "");
        HeroNode cur = head.next;//辅助指针
        HeroNode next = null; //指向当前节点[cur]的下一个节点

        while(true) {
            if(cur == null) {
                break;
            }
            next = cur.next; //先暂时保存当前节点的下一个节点，后面用于cur后移
            cur.next = newhead.next; //将cur的下一个节点指向新链表最前的节点
            newhead.next = cur; //新链表头节点指向当前节点
            cur = next; //cur后移

        }
        //原头节点指向新链表最前的节点
        head.next = newhead.next;
    }

    //实现链表反向打印，利用栈的先进后出特点
    public void reversePrint() {
        //空链表，不打印
        if(head.next == null) {
            return;
        }
        Stack<HeroNode> stack = new Stack<HeroNode>();
        HeroNode cur = head.next;
        while(cur != null) {
            stack.push(cur);//压入栈
            cur = cur.next;
        }
        //将栈中节点pop出栈打印
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }

    //查找倒数第K个节点
    public HeroNode search(int k) {
        //先把链表从头到尾遍历。得到链表总长度
        int length = count();
        //效验k
        if(k <= 0 || k > length) {
            return null;
        }
        HeroNode temp = head.next;
        //遍历到length-k就是倒数第k个节点
        for(int j = 0; j < length - k; j++) {
            temp = temp.next;
        }
        return temp;
    }

    //求单链表有效节点的个数
    public int count() {
        if(head.next == null) {
            System.out.println("链表空");
            return 0;
        }
        int count = 0;
        HeroNode temp = head.next;
        while (true) {
            if(temp == null) {
                break;
            }
            count++;
            temp = temp.next;
        }
        return count;
    }

    //修改节点信息
    public void update(HeroNode newHero) {
        if(head.next == null) {
            System.out.println("链表空");
            return;
        }
        HeroNode temp = head.next;
        boolean flag = false;
        while (true) {
            if(temp == null) {
                break;
            }
            if(temp.no == newHero.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag) {
            temp.name = newHero.name;
            temp.nickname = newHero.nickname;
        } else {
            System.out.println("没有找到");
        }

    }

    //按编号顺序插入
    public void addByOrder(HeroNode heroNode) {
        if(head.next == null) {
            head.next = heroNode;
            return;
        }
        HeroNode temp = head.next;
        boolean flag = false; //标志添加的节点编号是否存在
        while (true) {

            if(temp.next == null) {
                break;
            }
            if(temp.next.no > heroNode.no) { //位置找到，就在temp的后面插入
                break;
            } else if (temp.next.no == heroNode.no) { //要添加的节点编号已存在
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag) {
            System.out.println("已存在");
            return;
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }


    }

    //遍历
    public void list() {
        if(head.next == null) {
            System.out.println("链表空");
        }
        HeroNode temp = head.next;
        while (true) {
            if(temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

}

//定义HeroNode，每个HeroNode对象就是一个节点
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;//指向下一个节点

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}
